package 数组算法;

import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class majorityElement169 {
    /**
     * 可以采用的遍历的方式的
     * <p>
     * 但是也是可以将数组作为Hashmp的一种数据结构 来记录相关的顺序
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        // 排序中间的元素可定是大于一半以上的
        Arrays.sort(nums);
        return nums[nums.length >> 1];
    }

    /**
     * 采用的hashmap的表的来进行来判断
     *
     * @param nums
     * @return
     */
    public int majorityElementV2(int[] nums) {
        Map<Integer, Long> map = Arrays.stream(nums).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        long limit = nums.length >> 1;
        for (Map.Entry<Integer, Long> entry : map.entrySet()) {
            if (entry.getValue() > limit) {
                return entry.getKey();
            }
        }
        return -1;
    }

    /**
     * m摩尔投票的来实现
     *
     * @param nums
     * @return
     */
    public int majorityElementV3(int[] nums) {
        int count = 0;
        int curr = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                curr = nums[i];
                count++;
            } else if (curr == nums[i]) {
                count++;
            } else {
                count--;
            }
        }
        return curr;
    }
}
